#include "bst_tree.h"




bool bst_tree_insert(bst_tree *r, int data)
{
    while ( NULL != r[0] )
    {
        if (data > r[0]->data) {
            r = &(r[0]->right);
        }
        else if (data < r[0]->data) {
            r = &(r[0]->left);
        }
        else {
            return false;
        }
    }

    bst_tree nd = (bst_tree) malloc(sizeof(bst_tree_node));
    nd->left    = NULL;
    nd->right   = NULL;
    nd->data    = data;

    *r = nd;

    return true;
}
bool bst_tree_find(bst_tree *r, int data)
{
    return bst_tree_lookup(r, data) != NULL;
}
bool bst_tree_delete(bst_tree *r, int data)
{
    bst_tree del_node = bst_tree_lookup(r, data);
    if (NULL == del_node)
        return false;
    bst_tree del_pa = bst_tree_lookup_pa(r, del_node);

    bst_tree rep_node = bst_tree_get_replace(del_node);
    bst_tree rep_pa   = bst_tree_lookup_pa(r, rep_node); 
    bst_tree_set_child(rep_pa, rep_node, NULL);
    bst_tree_set_child(del_pa, del_node, rep_node);
    if ( NULL != rep_node ) {
        rep_node->left   = del_node->left;
        rep_node->right  = del_node->right;
    }
    del_node->left = NULL;
    del_node->right = NULL;
    if (*r == del_node)
        *r = rep_node;
    free(del_node);
    
    return true;
}
bst_tree bst_tree_lookup( bst_tree *r, int data)
{
    while ( NULL != r[0])
    {
        if ( data > r[0]->data)
            r = &(r[0]->right);
        else if ( data < r[0]->data)
            r = &( r[0]->left);
        else
            break;
    }
    return r[0];
}
bst_tree bst_tree_lookup_pa( bst_tree *r, bst_tree tag)
{
    if (tag == NULL || tag == *r)
        return NULL;
    
    bst_tree pa = *r;
    int data = tag->data;

    while ( pa ){
        if ( pa->right && pa->right->data == data)
            return pa;
        else if ( pa->left && pa->left->data == data )
            return pa;
        else if (data > pa->data)
            pa = pa->right;
        else 
            pa = pa->left;
    }

    return pa;
}

bst_tree bst_tree_get_replace(bst_tree r)
{
    bst_tree ln = r->left;
    while (ln && ln->right)
        ln = ln->right;
    bst_tree rn = r->right;
    while (rn && rn->left)
        rn = rn->left;

    return ln != NULL ? ln : rn;
}

void bst_tree_set_child(bst_tree pa, bst_tree old_ch, bst_tree new_ch)
{
    if (NULL == pa)
        return ;

    if ( pa->left == old_ch)
        pa->left = new_ch;
    else if ( pa->right == old_ch)
        pa->right = new_ch;

    
}

void bst_tree_free(bst_tree *r)
{
    if ( NULL == *r)
        return ;
    bst_tree_free( &(r[0]->left));
    bst_tree_free( &(r[0]->right));
    free( *r );
    *r = NULL;
}